﻿using System;
using System.Collections.Generic;
using System.Text;

namespace PrimeNumberofSetBitsinBinaryRepresentation
{
    public class Solution
    {
        /// <summary>
        /// 1位为素数的数量
        /// </summary>
        /// <param name="L">开始</param>
        /// <param name="R">结束</param>
        /// <returns>素数数量</returns>
        public int CountPrimeSetBits(int L, int R)
        {
            int count = 0;
            for (int i = L; i <= R; i++)
            {
                int bits = CountBitsOfNumber(i);
                if (IsPrime(bits))
                {
                    count++;
                }
            }

            return count;
        }

        private int CountBitsOfNumber(int n)
        {
            int count = 0;
            while (n != 0)
            {
                count += n % 2;
                n /= 2;
            }

            return count;
        }

        /// <summary>
        /// 判断素数
        /// </summary>
        /// <param name="n">数字</param>
        /// <returns>true/false</returns>
        private bool IsPrime(int n)
        {
            if (n == 1)
                return false;

            for (int i = 2; i <= n / 2; i++)
                if (n % i == 0)
                    return false;
            
            return true;
        }
    }
}
